|
Ein bedeutendes Resultat von Eilenberg zeigt die bijektive
Korrespondenz von Varietäten endlicher Monoide und Varietäten von
Sprachen. Ebenso wie bestimmte Operationen auf einzelnen Sprachen
Entsprechungen auf ihren syntaktischen Monoiden haben, kann man die
Frage nach algebraischen Entsprechungen von Operationen auf
Varietäten von Sprachen stellen.
Zwei interessante Operationen auf Varietäten von Sprachen sind das
Bilden von Polynomen als endliche Vereinigungen von Sprachen der
Form L_0 a_1 L_1 ... a_n L_n, wobei die a_i einzelne Zeichen sind,
und das Bilden von eindeutigen Polynomen, bei denen man zusätzlich
fordert, daß jedes Wort aus der resultierenden Sprache genau eine
passende Faktorisierung besitzt. Arbeiten von Schützenberger, Pin,
Straubing und Thérien zeigten schließlich, daß der eindeutige
polynomielle Abschluß als algebraische Entsprechung das
Mal'cev-Produkt mit der Varietät LI hat. Pin und Weil konnten
zeigen, daß auch der polynomielle Abschluß einem
Mal'cev-Produkt entspricht, nämlich dem mit der Varietät
geordneter Halbgruppen LJ+.
Wir stellen die erwähnten Ergebnisse über Wörtern und deren
Beweise sowie die notwendigen Hintergründe vor. Soweit möglich,
werden die Ergebnisse auf Spuren übertragen. Eine besondere Rolle
wird hierbei der Varietät DA zukommen.
|